# -*- coding: utf-8 -*-
# 给定一个没有重复数字的序列，返回其所有可能的全排列

# 示例:
# 输入: [1,2,3]
# 输出:
# [
#   [1,2,3],
#   [1,3,2],
#   [2,1,3],
#   [2,3,1],
#   [3,1,2],
#   [3,2,1]
# ]

# # 使用递归调用的方法输出全排列
# class Solution(object):
#     def permute(self, nums):
#         """
#         :type nums: List[int]
#         :rtype: List[List[int]]
#         """
#         if len(nums) <= 1:
#             return [nums];

#         if len(nums) == 2:
#             rtn = [];
#             rtn.append([ nums[0], nums[1] ]);
#             rtn.append([ nums[1], nums[0] ]);
#             return rtn;

#         rtn = [];

#         for i in xrange(0, len(nums)):
#             temp = [nums[i]];
#             nums.pop(i);
#             sub = self.permute(nums);
#             for j in xrange(0, len(sub)):
#                 rtn.append(temp + sub[j]);
#             nums.insert(i, temp[0]);

#         return rtn;







# 使用回溯法解决问题
# 解题思路：
# 原数组: [1,2,3]
# 1、第一步确定[0]的元素，衍生出以下3中情况
# [1,2,3] [2,1,3] [3,1,2]
# 2、拿上面的[1,2,3]为例，[0]的元素已经确定，继续确定[1]的元素
# [1,2,3] [1,3,2]
# 
# 问题被分割为上面的2个步骤，多次迭代后就能解决问题
class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        def backtrack(index):
            if index == len(nums):
                rtn.append(nums[:]);
                return;
            for i in xrange(index, n):
                nums[index], nums[i] = nums[i], nums[index];
                backtrack(index + 1);
                nums[index], nums[i] = nums[i], nums[index];


        rtn = [];
        n = len(nums);
        backtrack(0);
        return rtn;



t = Solution()
print t.permute([1, 2, 3]);